{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Dice Rolls With Target Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numRollsToTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #掷骰子等于目标和的方法数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>这里有&nbsp;<code>n</code>&nbsp;个一样的骰子，每个骰子上都有&nbsp;<code>k</code>&nbsp;个面，分别标号为&nbsp;<code>1</code>&nbsp;到 <code>k</code> 。</p>\n",
    "\n",
    "<p>给定三个整数 <code>n</code> ,&nbsp; <code>k</code> 和&nbsp;<code>target</code>&nbsp;，返回可能的方式(从总共<em>&nbsp;</em><code>k<sup>n</sup></code><em>&nbsp;</em>种方式中)滚动骰子的数量，使正面朝上的数字之和等于<em>&nbsp;</em><code>target</code>&nbsp;。</p>\n",
    "\n",
    "<p>答案可能很大，你需要对&nbsp;<code>10<sup>9</sup>&nbsp;+ 7</code> <strong>取模</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, k = 6, target = 3\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>你扔一个有 6 个面的骰子。\n",
    "得到 3 的和只有一种方法。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, k = 6, target = 7\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>你扔两个骰子，每个骰子有 6 个面。\n",
    "得到 7 的和有 6 种方法：1+6 2+5 3+4 4+3 5+2 6+1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 30, k = 30, target = 500\n",
    "<strong>输出：</strong>222616187\n",
    "<strong>解释：</strong>返回的结果必须是对 10<sup>9</sup> + 7 取模。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n, k &lt;= 30</code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-dice-rolls-with-target-sum](https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-dice-rolls-with-target-sum](https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n6\\n3', '2\\n6\\n7', '30\\n30\\n500']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n",
    "        memo = dict()\n",
    "        res = self.dfs(d, f, 0, 0, target, memo)\n",
    "        return res % (10**9+7)\n",
    "    \n",
    "    def dfs(self, d, f, cur_dice, _sum, target, memo):\n",
    "        if _sum == target and cur_dice == d:\n",
    "            return 1\n",
    "        if cur_dice == d and _sum != target:\n",
    "            return 0\n",
    "        if (_sum, cur_dice) in memo:\n",
    "            return memo[(_sum, cur_dice)]\n",
    "        cur_res = 0\n",
    "        for j in range(1, f+1):\n",
    "            if _sum + j <= target and cur_dice + 1 <= d:\n",
    "                cur_res +=  self.dfs(d, f, cur_dice+1, _sum+j, target, memo)\n",
    "        memo[(_sum, cur_dice)] = cur_res\n",
    "        return cur_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n",
    "        if d*f < target or target<d: return 0\n",
    "        mod = 10**9 + 7\n",
    "        # dp = collections.defaultdict(int)\n",
    "        # def dfs(k,s):\n",
    "        #     if (k,s) in dp or k<=0 or s<=0:\n",
    "        #         return dp[(k,s)]\n",
    "        #     if k==1 and s<=f: return 1\n",
    "        #     for i in range(1,f+1):\n",
    "        #         dp[(k,s)] += dfs(k-1,s-i)\n",
    "        #     dp[(k,s)] %= mod\n",
    "        #     return dp[(k,s)]\n",
    "        # return dfs(d,target)\n",
    "        dp=[1]*f\n",
    "        for i in range(1,d):\n",
    "            limit = min(target, f*(i+1))\n",
    "            dp = [sum(dp[max(0,j-f):j])%mod for j in range(limit)]\n",
    "        return dp[target-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef numRollsToTarget(self,d,f,target):\n",
    "\t\tdp=[0]*(target+1) #dp数组\n",
    "\t\tfor i in range(1,d+1): #这一层的是次数\n",
    "\t\t\tt_sum=0+i==1 #这个i==1是为了解决i==1时的差异性问题 可以自行模拟一下 t_sum保存一个连续段的和\n",
    "\t\t\tnew_dp=[0]*(target+1)\n",
    "\t\t\tfor j in range(min(target,f*i)): #min算是一个小优化\n",
    "\t\t\t\tt_sum+=dp[j]\n",
    "\t\t\t\tif j>f: #假如说f=6 new_dp[5]=sum(dp[:5]) new_dp[6]=sum(dp[:6]) new_dp[7]=sum(dp[1:7])...\n",
    "\t\t\t\t\tt_sum-=dp[j-f]\n",
    "\t\t\t\tnew_dp[j+1]=t_sum #不能是+=\n",
    "\t\t\tdp=new_dp\n",
    "\t\treturn dp[-1]%(10**9+7) #python3倒是不需要担心溢出的问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n",
    "        if not d:\n",
    "            return 0\n",
    "        dp = [0] * (target+1)\n",
    "        for i in range(1, target+1):\n",
    "            if i <= f:\n",
    "                dp[i] = 1\n",
    "        for i in range(1, d):\n",
    "            for j in range(target, 0, -1):\n",
    "                start = j-f if j-f >= 0 else 0\n",
    "                dp[j] = sum(dp[start:j]) % 1000000007\n",
    "        return dp[target] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n",
    "        if target > d * f:\n",
    "            return 0\n",
    "\n",
    "        dp = [0] * (target + 1)\n",
    "        \n",
    "        for j in range(1, min(f, target) + 1):\n",
    "            dp[j] = 1\n",
    "        \n",
    "        for i in range(2, d + 1):\n",
    "            for j in range(min(target, i * f), i - 1, -1):\n",
    "                dp[j] = 0\n",
    "\n",
    "                for v in range(1, min(j, f + 1)):\n",
    "                    dp[j] += dp[j - v]\n",
    "\n",
    "            dp[i - 1] = 0\n",
    "\n",
    "        return dp[target] % 1000000007\n",
    "\n",
    "        # dp = [[0] * (target + 1) for _ in range(d + 1)]\n",
    "        \n",
    "        # for j in range(1, min(f, target) + 1):\n",
    "        #     dp[1][j] = 1\n",
    "        \n",
    "        # for i in range(2, d + 1):\n",
    "        #     for j in range(i, min(target, i * f) + 1):\n",
    "        #         for v in range(1, min(j, f + 1)):\n",
    "        #             dp[i][j] += dp[i - 1][j - v]\n",
    "\n",
    "        # return dp[d][target] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for j in range(1, f + 1):\n",
    "            dic[j] = 1\n",
    "        for _ in range(1, d):\n",
    "            temp = collections.defaultdict(int)\n",
    "            for k, v in dic.items():\n",
    "                for j in range(1, f + 1):\n",
    "                    if k + j <= target:\n",
    "                        temp[k + j] += v\n",
    "            dic = temp\n",
    "        return dic[target] % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n",
    "        if target < d or target > d*f:\n",
    "            return 0\n",
    "        \n",
    "        dp = [[0]*(target+1) for _ in range(d+1)]\n",
    "\n",
    "        for i in range(1, min(f, target) + 1):\n",
    "            dp[1][i] = 1\n",
    "        \n",
    "        for i in range(2, d + 1):\n",
    "            for j in range(i, target + 1):\n",
    "                for k in range(1, min(j, f) + 1):\n",
    "                    dp[i][j] += dp[i-1][j-k]\n",
    "        \n",
    "        return dp[d][target] % (pow(10, 9) + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n",
    "        if target > f*d:\n",
    "            return 0\n",
    "        dp = [([0 for i in range(f*d+1)])for i in range(d+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(d):\n",
    "            for j in range(f*d):\n",
    "                if not dp[i][j]:\n",
    "                    continue\n",
    "                for k in range(1, f+1):\n",
    "                    dp[i+1][j+k]+=dp[i][j]\n",
    "        return dp[-1][target]%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = {}\n",
    "        self.m = 10 ** 9 + 7\n",
    "    def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n",
    "        if (d, f, target) in self.memo:\n",
    "            return self.memo[(d, f, target)]\n",
    "        if target <= 0:\n",
    "            return 0\n",
    "        if d == 1 and target <= f:\n",
    "            return 1\n",
    "        if d == 1 and target > f:\n",
    "            return 0\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1, f + 1):\n",
    "            ans += self.numRollsToTarget(d - 1, f, target - i)\n",
    "        ans = ans % self.m\n",
    "        self.memo[(d, f, target)] = ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, x: int, target: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        # dp[i][j] 表示前 i 个骰子和为 j 的个数\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "        for i in range(n):\n",
    "            for j in range(target, -1, -1):\n",
    "                dp[j] = 0\n",
    "                for k in range(1, min(x, j) + 1):\n",
    "                    dp[j] = (dp[j] + dp[j - k]) % MOD\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        MOD = (10 ** 9 + 7)\n",
    "        dp = [[0] * (target + 1) for _ in range(2)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            now, pre = i % 2, (i + 1) % 2\n",
    "            dp[now][0] = 0\n",
    "            for j in range(1, target + 1):\n",
    "                dp[now][j] = 0\n",
    "                for l in range(1, min(k + 1, j + 1)):\n",
    "                    dp[now][j] += dp[pre][j - l]\n",
    "                dp[now][j] %= MOD\n",
    "        return dp[n % 2][target] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        total = n * k\n",
    "        if target > total:\n",
    "            return 0\n",
    "            \n",
    "        last = [0] * (total + 1)\n",
    "        last[0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            new = [0] * (total + 1)\n",
    "            for j in range(total + 1):\n",
    "                for x in range(1, k + 1):\n",
    "                    if j < x:\n",
    "                        continue \n",
    "                    else:\n",
    "                        new[j] += last[j - x]\n",
    "            last = new \n",
    "        # print(last)\n",
    "        return last[target] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        dp = [[0]*(target+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, target+1):\n",
    "                for num in range(1, k+1):\n",
    "                    if j >= num:\n",
    "                        dp[i][j] = (dp[i][j] + dp[i-1][j-num]) % (10**9+7)\n",
    "        \n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 3, 3, 3\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [0] * (target + 1)\n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(target, -1, -1):\n",
    "                dp[j] = 0\n",
    "                for x in range(1, k + 1):\n",
    "                    if j - x >= 0:\n",
    "                        dp[j] += dp[j - x] % MOD\n",
    "                dp[j] %= MOD\n",
    "        return dp[-1] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    constant = 10 ** 9 + 7\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if target >= n * k:\n",
    "            return 1 if target == n * k else 0\n",
    "        self.dp = [0] * (target + 1)\n",
    "        self.dp[0] = 1\n",
    "        for round in range(n):\n",
    "            left_index = max(0,target - k)\n",
    "            now_sum = sum(self.dp[left_index:target])\n",
    "            for val in range(target,round-1,-1):\n",
    "                self.dp[val] = now_sum\n",
    "                now_sum -= self.dp[val-1]\n",
    "                left_index -= 1\n",
    "                if left_index >=0:\n",
    "                    now_sum += self.dp[left_index]\n",
    "            for each in range(1,round-1):\n",
    "                self.dp[each] = 0\n",
    "        return self.dp[-1] % Solution.constant"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if not n:\n",
    "            return 0\n",
    "        dp = [0] * (target+1)\n",
    "        for i in range(1, target+1):\n",
    "            if i <= k:\n",
    "                dp[i] = 1\n",
    "        for i in range(1, n):\n",
    "            for j in range(target, 0, -1):\n",
    "                start = j-k if j-k >= 0 else 0\n",
    "                dp[j] = sum(dp[start:j]) % 1000000007\n",
    "        return dp[target] \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        \"\"\"\n",
    "        分组背包问题\n",
    "        dp[i][j] 表示扔 i 个骰子，组成 amount=j 的组合数量\n",
    "\n",
    "        枚举第 i 个骰子是 1~k\n",
    "        dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... dp[i-1][j-k]\n",
    "        \"\"\"\n",
    "        if target < n:\n",
    "            return 0\n",
    "        m = 10 ** 9 + 7\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(target+1):\n",
    "                if i == 0:\n",
    "                    for k in range(1, k+1):\n",
    "                        if j == k:\n",
    "                            dp[i][j] = 1\n",
    "                else:\n",
    "                    for k in range(1, k+1):\n",
    "                        if j-k >= 0:\n",
    "                            dp[i][j] = (dp[i][j]+dp[i-1][j-k]) % m\n",
    "        \n",
    "        return dp[n-1][target] % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if target > n * k or target < n:\n",
    "            return 0\n",
    "        \n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        dp = [[0] * (target+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(i, min(target+1, i*k+1)):\n",
    "                for x in range(1, min(k+1, j+1)):\n",
    "                    dp[i][j] += dp[i-1][j-x]\n",
    "        return dp[n][target] % MOD\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\r\n",
    "        dp = []\r\n",
    "        for _ in range(n+1):\r\n",
    "            tmp = []\r\n",
    "            for _ in range(target+1):\r\n",
    "                tmp.append(0)\r\n",
    "            dp.append(tmp)\r\n",
    "        # for i in range(1, k+1):\r\n",
    "        #     if i <= target: dp[1][i] = 1\r\n",
    "        dp[0][0] = 1\r\n",
    "        \r\n",
    "        for i in range(1, n+1):\r\n",
    "            for capacity in range(target+1):\r\n",
    "                for j in range(1, k+1):\r\n",
    "                    if capacity >= j:\r\n",
    "                        dp[i][capacity] += dp[i-1][capacity-j]\r\n",
    "        return dp[n][target]%(10**9+7)\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if target < n:\n",
    "            return 0\n",
    "        if target > k * n:\n",
    "            return 0\n",
    "        dp = [[0 for _ in range(target + 1)] for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, target + 1):\n",
    "                count = 0\n",
    "                for x in range(1, k + 1):\n",
    "                    if j - x >= 0:\n",
    "                        count += dp[i - 1][j - x]\n",
    "                dp[i][j] = count\n",
    "        print(dp)\n",
    "        return dp[-1][-1] % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    MOD = int(1e9 + 7)\n",
    "    @lru_cache(maxsize=5000)\n",
    "    def mr(self, n, k, t) -> int:\n",
    "        if t > n * k or t <= 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        for i in range(1, k + 1):\n",
    "            ans += self.mr(n - 1, k, t - i)\n",
    "            ans %= self.MOD\n",
    "        return int(ans)\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if target > n * k:\n",
    "            return 0\n",
    "        return self.mr(n, k, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        save = dict()\n",
    "        def dfs(n:int,k:int,target:int) -> int:\n",
    "            if save.get((n, k, target)) is not None:\n",
    "                return save[(n, k, target)]\n",
    "            if n == 1:\n",
    "                if(target>k):\n",
    "                    return 0\n",
    "                else:\n",
    "                    return 1\n",
    "            \n",
    "            s = 0\n",
    "            for i in range(1,k+1):\n",
    "                if (n-1)*k+i >= target:\n",
    "                    if target - i>0:\n",
    "                        s += dfs(n-1,k,target-i)\n",
    "                        s%=10**9+7\n",
    "            save[(n, k, target)] = s\n",
    "            return s\n",
    "        \n",
    "        return dfs(n,k,target)%(10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(n_, t_):\n",
    "            if n_ == 1: return int(t_ <= k)\n",
    "            return sum(dfs(n_ - 1, t_ - i) for i in range(max(1, t_ - k * (n_ - 1)), min(k, t_ - n_ + 1) + 1)) % 1000000007\n",
    "        return dfs(n, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    cache = {}\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if target > n * k or target < n:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if (n, k, target) in self.cache:\n",
    "            return self.cache[(n, k, target)]\n",
    "        res = 0\n",
    "        for i in range(1, k+1):\n",
    "            res += self.numRollsToTarget(n-1, k, target-i)\n",
    "            # print(i, res)\n",
    "        res = res % (10 ** 9 + 7)\n",
    "        self.cache[(n, k, target)] = res\n",
    "        # print(self.cache)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if not (n <= target <= n * k):\n",
    "            return 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == 0:\n",
    "                return int(j == 0)\n",
    "            res = 0\n",
    "            for x in range(min(k, j + 1)):\n",
    "                res += dfs(i - 1, j - x)\n",
    "            return res % MOD\n",
    "        return dfs(n, target - n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 会超时的递归代码\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if not (n <= target <= n * k):\n",
    "            return 0  # 无法组成 target\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if j < 0:\n",
    "                return 0  # j 不能是负数\n",
    "            if i == 0:\n",
    "                return int(j == 0)\n",
    "            res = 0\n",
    "            for x in range(1, k + 1):  # 掷出了 x\n",
    "                res += dfs(i - 1, j - x)\n",
    "            return res % MOD\n",
    "        return dfs(n, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 会超时的递归代码\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if not (n <= target <= n * k):\n",
    "            return 0  # 无法组成 target\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if j < 0:\n",
    "                return 0  # j 不能是负数\n",
    "            if i == 0:\n",
    "                return int(j == 0)\n",
    "            res = 0\n",
    "            for x in range(1, k + 1):  # 掷出了 x\n",
    "                res += dfs(i - 1, j - x)\n",
    "            return res % MOD\n",
    "        return dfs(n, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        # lst_num=[[0 for _ in range(target+1)] for _ in range(n)]\n",
    "        # for i in range(1,min(k+1,target+1)):\n",
    "        #     lst_num[0][i]=1\n",
    "        \n",
    "        # for row in range(1,n):\n",
    "        #     for j in range(1,target+1):\n",
    "        #         for i in range(1,min(k+1,j)):\n",
    "        #             lst_num[row][j]+=lst_num[row-1][j-i]\n",
    "        #             lst_num[row][j] %=int(1e9+7)\n",
    "        \n",
    "        # return lst_num[n-1][target]\n",
    "\n",
    "        @lru_cache(100000)\n",
    "        def get_num(n, target):\n",
    "            if target <= n - 1 or target > n * k:\n",
    "                return 0\n",
    "            if n == 1 and target <= k:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for i in range(1, k + 1):\n",
    "                ans += get_num(n - 1, target - i)\n",
    "            return ans % 1000000007\n",
    "        \n",
    "        return get_num(n, target)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if target < n or target > n * k:\n",
    "            return 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(n, t):\n",
    "            if n == 1:\n",
    "                return 1 if 0 < t <= k else 0\n",
    "            acc = 0\n",
    "            for i in range(1, k + 1):\n",
    "                acc += dfs(n - 1, t - i)\n",
    "            return acc\n",
    "        \n",
    "        return dfs(n, target) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def dfs(self, n, k, target, mod):\n",
    "        if n * k < target or target < n:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        \n",
    "        res = 0\n",
    "        for t in range(1, k + 1):\n",
    "            res += self.dfs(n - 1, k, target - t, mod)\n",
    "            res %= mod\n",
    "\n",
    "        return res % mod\n",
    "\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        return self.dfs(n, k, target, int(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    @cache\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if not (n <= target <= n * k):\n",
    "            return 0  # 无法组成 target\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        for i in range(1, k+1):\n",
    "            ans += self.numRollsToTarget(n - 1, k, target - i)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        if target > n * k or target < n:\n",
    "            return 0\n",
    "        mod = 10**9 + 7\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(curN, curTarget):\n",
    "            if curN == 0:\n",
    "                if curTarget == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for x in range(1, k+1):\n",
    "                ans += dfs(curN - 1, curTarget - x) % mod\n",
    "            return ans % mod\n",
    "        return dfs(n, target)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        self.res = 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(n, curSum):\n",
    "            print(n,curSum)\n",
    "            if( n <= 0):\n",
    "                if(curSum == target):\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if(curSum >= target):\n",
    "                return 0\n",
    "\n",
    "            sum1 = 0\n",
    "            for i in range(1,k + 1):\n",
    "                if(i <= target - curSum and n >= 1):\n",
    "                    sum1 = sum1 + dfs(n-1, curSum + i)\n",
    "            return sum1 % (10**9 + 7)\n",
    "        \n",
    "        return dfs(n, 0)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(roll_num,target,k):\n",
    "            res =0 \n",
    "            MOD = 10 ** 9 + 7\n",
    "            if roll_num== 0:\n",
    "                if target ==0:res = 1\n",
    "            else:\n",
    "                for i in range(1,k+1):\n",
    "                    if i<=target:\n",
    "                        res += dfs(roll_num-1,target-i,k) % MOD\n",
    "            return res % MOD\n",
    "\n",
    "        return dfs(n,target,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i,j)->int:\n",
    "            if i==0:\n",
    "                return 1 if j==0 else 0\n",
    "            if j<=0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for h in range(1,k+1):\n",
    "                ans += dfs(i-1,j-h)\n",
    "            return ans%mod\n",
    "        return dfs(n,target)\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        def dfs(res, i):\n",
    "            if (res, i) in h:\n",
    "                return h[(res, i)]\n",
    "            if i == 2:\n",
    "                if res < i or res > i * k:\n",
    "                    return 0\n",
    "                elif res <= k + 1:\n",
    "                    return res - 1\n",
    "                else:\n",
    "                    return i * k - res + 1\n",
    "            else:\n",
    "                ans = 0\n",
    "                for j in range(k):\n",
    "                    ans += dfs(res - j - 1, i - 1)\n",
    "            h[(res, i)] = ans % MOD\n",
    "            return ans % MOD\n",
    "\n",
    "        h = dict()\n",
    "        if n == 1:\n",
    "            if target <= k:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        return dfs(target, n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numRollsToTarget(self, n: int, k: int, target: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        @cache \n",
    "        def f(ni: int, t: int) -> int:          #ni个骰子之和等于t的方法数\n",
    "            if ni == 0:\n",
    "                if t == 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            if t < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for i in range(1, k + 1):       #枚举每个可能骰出的数\n",
    "                ans = (ans + f(ni - 1, t - i)) % mod\n",
    "            return ans % mod\n",
    "\n",
    "        return f(n, target)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
